第4题【说明】
一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路劲。一种求解无向图上哈密尔顿回路算法的基础私下如下:
假设图G存在一个从顶点V
0出发的哈密尔顿回路V
0——V
1——V
2——V
3——...——V
n-1——V
0。算法从顶点V
0出发,访问该顶点的一个未被访问的邻接顶点V
1,接着从顶点V
1出发,访问V
1一个未被访问的邻接顶点V
2,对顶点V
i,重复进行以下操作:访问V
i的一个未被访问的邻接接点V
i+1;若V
i的所有邻接顶点均已被访问,则返回到顶点V
i-1,考虑V
i-1的下一个未被访问的邻接顶点,仍记为V
i;直到找到一条哈密尔顿回路或者找不到哈密尔顿回路,算法结束。
【C代码】
下面是算法的C语言实现。
(1) 常量和变量说明
n:图G中的顶点数
c[][]:图G的邻接矩阵
K:统计变量,当期已经访问的定点数为k+1
x[k]:第k个访问的顶点编号,从0开始
Visited[x[k]]:第k个顶点的访问标志,0表示未访问,1表示已访问
(2) C程序